KMP子字符串查找算法

Author Avatar
Felix 5月 02, 2015

概述

算法的基本思想是：当出现不匹配时，就能知晓一部分文本的内容，可以利用这些信息避免将指针回退到所有这些已知的字符串之前。

DFA（确定有限状态机）模拟

提前判断如何重新查找，而这种判断只取决于模式本身，所以可以对模式的字符序列做一个确定有限状态机。

DFA的数据结构表示为二维数组dfa[R][M]，其中R为指定字典中的字符集的个数（比如ASCII为256），M为匹配字符串pat的长度，状态的意思是文本中某个位置i匹配pat的程度，0状态为未匹配状态，M状态为终止状态，找到了完整匹配的字符串。
如图中R=3，M=6，二维数组中的值指向下一个状态。

构造DFA

穷举模式pat的所有可能情况，将这些情况用状态图表示。其中X记录匹配失败时重启的索引位置。

编码实现

用暴力算法实现子字符串查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int search(String txt, String pat) {
     int i, N = txt.length();
     int j, M = pat.length();
     for (i = 0, j = 0; i < N && j < M; i++) {
         if (txt.charAt(i) == pat.charAt(j)) {
             j++;
         } else {  //显式回退
             i-=j;
             j=0;
         }
     }
     if (j==M) return i-M;
     return N;
 }

KMP查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
    * @return pat在txt中开始出现的位置，如果等于txt.length()表示没有找到
    */
   public int search(String txt) {
       int M = pat.length();
       int N = txt.length();
       int i, j;  //i指向txt，j指向pat
       for (i = 0, j = 0; i < N && j < M; i++) {
           j = dfa[txt.charAt(i)][j];
       }
       if (j == M) return i - M;   //匹配
       return N;                   //不匹配
   }

构造DFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private final int R;       // the radix
   private int[][] dfa;       // the KMP automoton
   private String pat;
   public KMP(String pat) {
       this.R = 256;   //设置字典大小
       this.pat = pat;
       //构造pat对应的dfa
       int M = pat.length();
       dfa = new int[R][M];
       dfa[pat.charAt(0)][0] = 1;
       for (int X = 0, j = 1; j < M; j++) {  //X记录匹配失败时的索引位置,j指向pat
           for (int c = 0; c < R; c++) {   //对于匹配失败的情况，直接复制重启状态
               dfa[c][j] = dfa[c][X];
           }
           dfa[pat.charAt(j)][j] = j + 1;           //匹配成功的指向下一个状态
           X = dfa[pat.charAt(j)][X]; //更新重启位置X
       }
   }

优缺点

优点：适合在长度不确定的输入流中进行查找，不需要在输入中回退。
缺点：最坏的情况（在重复性很高的文本中查找重复性很高的模式）在实际应用中很少出现，还不如使用暴力算法来的容易，性能也差不了多少。

参考

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne

expand_less